{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Keys and Rooms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: canVisitAllRooms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #钥匙和房间"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有 <code>n</code> 个房间，房间按从 <code>0</code> 到 <code>n - 1</code> 编号。最初，除 <code>0</code> 号房间外的其余所有房间都被锁住。你的目标是进入所有的房间。然而，你不能在没有获得钥匙的时候进入锁住的房间。</p>\n",
    "\n",
    "<p>当你进入一个房间，你可能会在里面找到一套不同的钥匙，每把钥匙上都有对应的房间号，即表示钥匙可以打开的房间。你可以拿上所有钥匙去解锁其他房间。</p>\n",
    "\n",
    "<p>给你一个数组 <code>rooms</code> 其中 <code>rooms[i]</code> 是你进入 <code>i</code> 号房间可以获得的钥匙集合。如果能进入 <strong>所有</strong> 房间返回 <code>true</code>，否则返回 <code>false</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<ol>\n",
    "</ol>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>rooms = [[1],[2],[3],[]]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>\n",
    "我们从 0 号房间开始，拿到钥匙 1。\n",
    "之后我们去 1 号房间，拿到钥匙 2。\n",
    "然后我们去 2 号房间，拿到钥匙 3。\n",
    "最后我们去了 3 号房间。\n",
    "由于我们能够进入每个房间，我们返回 true。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>rooms = [[1,3],[3,0,1],[2],[0]]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>我们不能进入 2 号房间。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == rooms.length</code></li>\n",
    "\t<li><code>2 &lt;= n &lt;= 1000</code></li>\n",
    "\t<li><code>0 &lt;= rooms[i].length &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= sum(rooms[i].length) &lt;= 3000</code></li>\n",
    "\t<li><code>0 &lt;= rooms[i][j] &lt; n</code></li>\n",
    "\t<li>所有 <code>rooms[i]</code> 的值 <strong>互不相同</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [keys-and-rooms](https://leetcode.cn/problems/keys-and-rooms/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [keys-and-rooms](https://leetcode.cn/problems/keys-and-rooms/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1],[2],[3],[]]', '[[1,3],[3,0,1],[2],[0]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:\n",
    "        sz = len(rooms)\n",
    "        A = [False for i in range(sz)]\n",
    "        A[0] = True\n",
    "        q = [0]\n",
    "        cnt = 1\n",
    "        while len(q) > 0:\n",
    "            front = q.pop(0)\n",
    "            room = rooms[front]\n",
    "            for i in room:\n",
    "                if not A[i]:\n",
    "                    A[i] = True\n",
    "                    q.append(i)\n",
    "                    cnt += 1\n",
    "        return cnt == sz"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canVisitAllRooms(self, rooms):\n",
    "        \"\"\"\n",
    "        :type rooms: List[List[int]]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        visit = [False for _ in rooms]\n",
    "        visit[0] = True\n",
    "        a = [0]\n",
    "        while a:\n",
    "            now = a.pop()\n",
    "            for k in rooms[now]:\n",
    "                if not visit[k]:\n",
    "                    a.append(k)\n",
    "                    visit[k] = True\n",
    "        \n",
    "        return sum(visit) == len(rooms)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canVisitAllRooms(self, rooms):\n",
    "        \"\"\"\n",
    "        :type rooms: List[List[int]]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        n, access, new = len(rooms), {0}, {0}\n",
    "        while new:\n",
    "            new = set(itertools.chain.from_iterable([rooms[item] for item in new])) - access\n",
    "            access |= new\n",
    "        return len(access) == n\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canVisitAllRooms(self, rooms: 'List[List[int]]') -> 'bool':\n",
    "        n = len(rooms)\n",
    "        unvisited = set(range(n))\n",
    "        keys = {0}\n",
    "        while len(keys):\n",
    "            cur = keys.pop()\n",
    "            if cur in unvisited:\n",
    "                keys.update(rooms[cur])\n",
    "                unvisited.remove(cur)\n",
    "        return len(unvisited) == 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canVisitAllRooms(self, rooms):\n",
    "        \"\"\"\n",
    "        :type rooms: List[List[int]]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        import queue\n",
    "        visit = [False for _ in rooms]\n",
    "        visit[0] = True\n",
    "        q = queue.Queue()\n",
    "        for  r in rooms[0]:\n",
    "            q.put(r)\n",
    "        \n",
    "        while not q.empty():\n",
    "            r = q.get()\n",
    "            if not visit[r]:\n",
    "                visit[r] = True\n",
    "                for k in rooms[r]:\n",
    "                    if not visit[k]:\n",
    "                        q.put(k)\n",
    "        \n",
    "        res = True\n",
    "        for e in visit:\n",
    "            res &= e\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canVisitAllRooms(self, rooms):\n",
    "        \"\"\"\n",
    "        :type rooms: List[List[int]]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        used_keys = []\n",
    "        unused_keys = []\n",
    "        unused_keys.extend(rooms[0])\n",
    "        while len(unused_keys) != 0:\n",
    "            key = unused_keys.pop()\n",
    "            if key in used_keys:\n",
    "                continue\n",
    "            used_keys.append(key)\n",
    "            unused_keys.extend(rooms[key])\n",
    "        if 0 in used_keys:\n",
    "            used_keys.remove(0)\n",
    "        return len(rooms) - 1 == len(used_keys)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canVisitAllRooms(self, rooms):\n",
    "        \"\"\"\n",
    "        :type rooms: List[List[int]]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if len(rooms) == 1:\n",
    "            return True\n",
    "        \n",
    "        if rooms[0] == []:\n",
    "            return False\n",
    "        \n",
    "        n = len(rooms)\n",
    "        mark = [0] * n\n",
    "        def open(i,keys):\n",
    "            mark[i] = 1\n",
    "            for key in keys:\n",
    "                if mark[key] == 1:\n",
    "                    continue\n",
    "                else:\n",
    "                    open(key,rooms[key])\n",
    "            return\n",
    "        open(0,rooms[0])\n",
    "        for i in mark:\n",
    "            if i == 0:\n",
    "                return False\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canVisitAllRooms(self, rooms):\n",
    "        \"\"\"\n",
    "        :type rooms: List[List[int]]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        def dfs(r, vis):\n",
    "            if r in vis:\n",
    "                return\n",
    "            vis.add(r)\n",
    "            for k in rooms[r]:\n",
    "                dfs(k, vis)\n",
    "        \n",
    "        vis=set()\n",
    "        dfs(0, vis)\n",
    "        \n",
    "        return len(vis)==len(rooms)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:\n",
    "        node_len = [0] * len(rooms)\n",
    "        Q = [0]\n",
    "        while Q:\n",
    "            node = Q.pop()\n",
    "            node_len[node] = 1\n",
    "            for i in range(len(rooms[node])):\n",
    "                if not node_len[rooms[node][i]]:\n",
    "                    Q.append(rooms[node][i])\n",
    "        return sum(node_len) == len(node_len)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canVisitAllRooms(self, rooms):\n",
    "        '''\n",
    "        思路:判断某个节点是否有向图的根:DFS\n",
    "        '''\n",
    "        N = len(rooms)\n",
    "        visited = [False] * N\n",
    "        queue = [0]\n",
    "        while queue:\n",
    "            vertex = queue.pop(0)\n",
    "            if visited[vertex]:\n",
    "                continue\n",
    "            visited[vertex] = True\n",
    "            for neighbor in rooms[vertex]:\n",
    "                queue.append(neighbor)\n",
    "        for visit in visited:\n",
    "            if not visit:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:\n",
    "        n = len(rooms)\n",
    "        keys = [0]\n",
    "        used = {0}\n",
    "        while keys:\n",
    "            next_keys = []\n",
    "            for k in keys:\n",
    "                for nk in rooms[k]:\n",
    "                    if nk not in used:\n",
    "                        used.add(nk)\n",
    "                        next_keys.append(nk)\n",
    "            keys = next_keys\n",
    "        return len(used) == n\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:\n",
    "        dq = deque(rooms[0])\n",
    "        walked_rooms = 1\n",
    "        walked = [False] * len(rooms)\n",
    "        walked[0] = True\n",
    "\n",
    "        while dq:\n",
    "            key = dq.pop()\n",
    "            if not walked[key]:\n",
    "                dq.extend(rooms[key])\n",
    "                walked[key] = True\n",
    "                walked_rooms += 1\n",
    "                #print(\"enter: %r\" % key)\n",
    "\n",
    "        return walked_rooms == len(rooms)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:\n",
    "        \n",
    "        visited = set()\n",
    "        queue = [rooms[0]]\n",
    "        visited.add(0)\n",
    "\n",
    "        while queue:\n",
    "            temp = queue.pop()\n",
    "            for num in temp:\n",
    "                if num not in visited:\n",
    "                    queue.append(rooms[num])\n",
    "                    visited.add(num)\n",
    "        \n",
    "        return len(visited) == len(rooms)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:\n",
    "        seen=set()\n",
    "        seen.add(0)\n",
    "        stack=rooms[0]\n",
    "        while stack:\n",
    "            key=stack.pop()\n",
    "            if key in seen or not key:continue\n",
    "            seen.add(key)\n",
    "            stack+=rooms[key]\n",
    "        if len(seen)==len(rooms):return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:\n",
    "        n = len(rooms)\n",
    "        num,visited = 0,{0}\n",
    "        queue = collections.deque([0])\n",
    "\n",
    "        while queue:\n",
    "            node = queue.popleft()  # 出队对首元素\n",
    "\n",
    "            for i in rooms[node]:\n",
    "                if i not in visited:\n",
    "                    visited.add(i)\n",
    "                    queue.append(i)\n",
    "        return len(visited)==n\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:\n",
    "        m=len(rooms)\n",
    "        seen=set([0])\n",
    "        queue=collections.deque([0])\n",
    "        \n",
    "        while queue:\n",
    "            tmp=queue.pop()\n",
    "            for i in rooms[tmp]:\n",
    "                if i not in seen:\n",
    "                    queue.append(i)\n",
    "                    seen.add(i)\n",
    "        return len(seen)==m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:\n",
    "        m=len(rooms)\n",
    "        seen=set([0])\n",
    "        stack=[0]\n",
    "        \n",
    "        while stack:\n",
    "            tmp=stack.pop()\n",
    "            for i in rooms[tmp]:\n",
    "                if i not in seen:\n",
    "                    stack.append(i)\n",
    "                    seen.add(i)\n",
    "        return len(seen)==m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:\n",
    "\n",
    "        def dfs(rooms, keys, hashset):\n",
    "            #访问这个房间可以访问的房子，并且还没有访问过的房子\n",
    "            if not keys:\n",
    "                return \n",
    "            for key in keys:\n",
    "                if key not in hashset:\n",
    "                    hashset.add(key)\n",
    "                    dfs(rooms, rooms[key], hashset)\n",
    "                else:\n",
    "                    continue \n",
    "        N = len(rooms)\n",
    "        hashset = set()\n",
    "        keys = [0]\n",
    "        dfs(rooms, keys, hashset)\n",
    "        if len(hashset) < N:\n",
    "            return False\n",
    "        else:\n",
    "            return True \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:\n",
    "        visited = set()\n",
    "        def dfs(x:int):\n",
    "            visited.add(x)\n",
    "            for i in rooms[x]:\n",
    "                if i not in visited:\n",
    "                    dfs(i)\n",
    "        dfs(0)\n",
    "        return len(rooms) == len(visited)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:\n",
    "        leng = len(rooms)\n",
    "        v = {0}  #set\n",
    "        stack = [0]  #栈：后进先出\n",
    "        while stack:\n",
    "            irooms = stack.pop()\n",
    "            for key in rooms[irooms]:\n",
    "                if key not in v:\n",
    "                    v.add(key)\n",
    "                    stack.append(key)\n",
    "        length = len(v)\n",
    "        if length == leng:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:\n",
    "        n = len(rooms)\n",
    "        queue = [0]\n",
    "        done = [0]\n",
    "        while queue:\n",
    "           cur = queue.pop(0)\n",
    "           #done.append(cur)\n",
    "           for i in rooms[cur]:\n",
    "               if i not in done:\n",
    "                   queue.append(i)\n",
    "                   done.append(i)\n",
    "        #print(done)\n",
    "        return len(done) == n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:\n",
    "        l = [0]\n",
    "        n = len(rooms)\n",
    "        flag = [0]*n\n",
    "        while l:\n",
    "            k = l.pop(0)\n",
    "            if flag[k]==0:\n",
    "                flag[k]=1\n",
    "                if rooms[k]:\n",
    "                    l.extend(rooms[k])\n",
    "        return sum(flag)==n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:\n",
    "        que = [rooms[0]]\n",
    "        visited = {0 : 1}\n",
    "\n",
    "        while len(que) > 0:\n",
    "            ele = que.pop(0)\n",
    "\n",
    "            all_visited = 1\n",
    "            #print(ele)\n",
    "            for r in ele:\n",
    "                if not visited.get(r):\n",
    "                    all_visited = 0\n",
    "                    visited[r] = 1\n",
    "                    que.append(rooms[r])                    \n",
    "                else:\n",
    "                    continue\n",
    "\n",
    "        #print(visited)\n",
    "        for i in range(1, len(rooms)):\n",
    "            if not visited.get(i):\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "        \n",
    "\n",
    "            \n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:\n",
    "        que = [rooms[0]]\n",
    "        visited = {0 : 1}\n",
    "\n",
    "        while len(que) > 0:\n",
    "            ele = que.pop(0)\n",
    "\n",
    "            all_visited = 1\n",
    "            #print(ele)\n",
    "            for r in ele:\n",
    "                if not visited.get(r):\n",
    "                    all_visited = 0\n",
    "                    visited[r] = 1\n",
    "                    que.append(rooms[r])                    \n",
    "                else:\n",
    "                    continue\n",
    "\n",
    "        print(visited)\n",
    "        for i in range(1, len(rooms)):\n",
    "            if not visited.get(i):\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "        \n",
    "\n",
    "            \n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:\n",
    "        visited = [False] * len(rooms)\n",
    "\n",
    "        def dfs(n: int):\n",
    "            if visited[n]:\n",
    "                return\n",
    "            visited[n] = True\n",
    "            for i in range(len(rooms[n])):\n",
    "                dfs(rooms[n][i])\n",
    "            return\n",
    "        dfs(0)\n",
    "        for i in range(len(rooms)):\n",
    "            if not visited[i]:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:\n",
    "        n = len(rooms)\n",
    "        arr, sets = [], set()\n",
    "        arr.append(rooms[0])\n",
    "        rooms[0] = []\n",
    "        sets.add(0)\n",
    "        while arr:\n",
    "            cur = arr.pop()\n",
    "            for ch in cur:\n",
    "                sets.add(ch)\n",
    "                arr.append(rooms[ch])\n",
    "                rooms[ch] = []\n",
    "        return True if len(sets) == n else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:\n",
    "    l = len(rooms)\n",
    "    q = [0]\n",
    "    m = [0] * l\n",
    "    m[0] = 1\n",
    "    c = 1\n",
    "    while len(q) > 0:\n",
    "      r = q.pop(0)\n",
    "      for n in rooms[r]:\n",
    "        if 0 == m[n]:\n",
    "          c += 1\n",
    "          m[n] = 1\n",
    "          q.append(n)\n",
    "    return c == l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bfs(self,visited,key,rooms):\n",
    "        q = collections.deque()\n",
    "        q.append(key)\n",
    "        visited[0]=True\n",
    "        while q:\n",
    "            index=q.popleft()\n",
    "            for nextIndex in rooms[index]:\n",
    "                if visited[nextIndex] == False:\n",
    "                    q.append(nextIndex)\n",
    "                    visited[nextIndex] = True\n",
    "\n",
    "    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:\n",
    "        visited=[False for i in range(len(rooms))]\n",
    "        self.bfs(visited,0,rooms)\n",
    "        for i in range(len(visited)):\n",
    "            if not visited[i]:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:\n",
    "        n = len(rooms)\n",
    "        checklist = [False] * n\n",
    "        for i in range(n):\n",
    "            q = deque()\n",
    "            q.append(0)\n",
    "            checklist[0] = True\n",
    "            while len(q) > 0:\n",
    "                cur_room = q.popleft()\n",
    "                for next_room in rooms[cur_room]:\n",
    "                    if checklist[next_room] == False:\n",
    "                        checklist[next_room] = True \n",
    "                        q.append(next_room)\n",
    "        return all(checklist)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self,visited,key,rooms):\n",
    "        if visited[key]:\n",
    "            return \n",
    "        visited[key]=True\n",
    "        keys=rooms[key]\n",
    "        for i in keys:\n",
    "            self.dfs(visited,i,rooms)\n",
    "    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:\n",
    "        visited=[False for i in range(len(rooms))]\n",
    "        self.dfs(visited,0,rooms)\n",
    "        for i in range(len(visited)):\n",
    "            if not visited[i]:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:\n",
    "        cache = [0]*len(rooms)\n",
    "\n",
    "        def visit(room):\n",
    "            if cache[room] == 1:\n",
    "                return\n",
    "            \n",
    "            cache[room] = 1\n",
    "            for key in rooms[room]:\n",
    "                visit(key)\n",
    "\n",
    "        visit(0)\n",
    "\n",
    "        return 0 not in cache"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
